home *** CD-ROM | disk | FTP | other *** search
/ Magnum One / Magnum One (Mid-American Digital) (Disc Manufacturing).iso / d20 / msgq160s.arc / BMG.C < prev    next >
Text File  |  1991-10-26  |  4KB  |  168 lines
  1. /*
  2.  * BMG.C - Search functions
  3.  *
  4.  * Msged/Q message editor for QuickBBS  Copyright 1990 by P.J. Muller
  5.  *
  6.  */
  7.  
  8. #include <string.h>
  9.  
  10. #include "msged.h"
  11. #include "bmg.h"
  12.  
  13. #ifdef BMGSEARCH
  14.  
  15. #include <ctype.h>
  16.  
  17. /*
  18.  *    bmg.c ->    Boyer-Moore-Gosper search routines
  19.  *
  20.  * Adapted from:
  21.  *   Boyer/Moore/Gosper-assisted 'egrep' search, with delta0 table as in
  22.  *   original paper (CACM, October, 1977).  No delta1 or delta2.  According to
  23.  *   experiment (Horspool, Soft. Prac. Exp., 1982), delta2 is of minimal
  24.  *   practical value.  However, to improve for worst case input, integrating
  25.  *   the improved Galil strategies (Apostolico/Giancarlo, Siam. J. Comput.,
  26.  *   February 1986) deserves consideration.
  27.  *
  28.  *   James A. Woods                    Copyright (c) 1986
  29.  *   NASA Ames Research Center
  30.  *
  31.  * 29 April 1986    Jeff Mogul    Stanford
  32.  *    Adapted as a set of subroutines for use by a program. No
  33.  *    regular-expression support.
  34.  *
  35.  * 29 August 1986    Frank Whaley    Beyond Words
  36.  *    Trimmed for speed and other dirty tricks.
  37.  */
  38.  
  39. /*  forward declarations  */
  40. #if !defined(__TURBOC__) && !defined(__JPIC__)
  41. static int strncmpi(char *, char *, int);
  42. #endif
  43.  
  44. /*
  45.  *    bmgCompile() ->    compile Boyer-Moore delta table
  46.  *
  47.  *    bmgCompile() compiles the delta table for the given search string, and
  48.  *     initializes the search argument structure.  This structure must be
  49.  *     passed to the bmgSearch() function described below.
  50.  */
  51. void bmgCompile(pat, arg, ignore)
  52.     char    *pat;        /*  the pattern        */
  53.     bmgARG    *arg;        /*  argument data    */
  54.     int    ignore;        /*  TRUE to ignore case    */
  55.     {
  56.     int    i,        /*  general ctr        */
  57.         patlen;        /*  pattern length    */
  58.  
  59.     patlen = strlen(pat);
  60.  
  61.     strcpy(arg->pat, pat);
  62.     if ((arg->ignore = (char) ignore) != 0)
  63.         strlwr(arg->pat);
  64.  
  65.     memset(arg->delta, patlen, 256);
  66.  
  67.     for (i = 0; i < patlen; ++i)
  68.         arg->delta[pat[i]] = (char) (patlen - i - 1);
  69.  
  70.     if (ignore)    /*  tweak upper case if ignore on  */
  71.         for (i = 0; i < patlen; ++i)
  72.             arg->delta[toupper(pat[i])] = (char) (patlen - i - 1);
  73.     }
  74.  
  75.  
  76. /*
  77.  *    bmgSearch() ->    scan for match
  78.  *
  79.  *    bmgSearch() performs a Boyer-Moore-Gosper search of the given buffer
  80.  *     for the string described by the given search argument structure.  The
  81.  *     match action function "action" will be called for each match found.
  82.  *     This function should return non-zero to continue searching, or 0 to
  83.  *     terminate the search.  bmgSearch() returns the total number of
  84.  *     matches found.
  85.  */
  86. int bmgSearch(buffer, buflen, arg)
  87.     char    *buffer;    /*  buffer to search        */
  88.     int    buflen;        /*  length of buffer        */
  89.     bmgARG    *arg;        /*  search argument        */
  90.     {
  91.     char    *s;        /*  temp ptr for comparisons    */
  92.     int    inc,        /*  position increment        */
  93.         k,        /*  current buffer index    */
  94.         patlen;        /*  pattern length        */
  95.  
  96.     k = (patlen = strlen(arg->pat)) - 1;
  97.  
  98.     for (;;)
  99.         {
  100.         while (((inc = arg->delta[buffer[k]]) != 0) &&
  101.             ((k += inc) < buflen))
  102.             ;
  103.         if (k >= buflen)
  104.             break;
  105.     
  106.         s = buffer + (k++ - (patlen - 1));
  107.         if (!(arg->ignore ? strncmpi(s, arg->pat, patlen) : strncmp(s, arg->pat, patlen)))
  108.             return (!0);
  109.         }
  110.  
  111.     return (0);
  112.     }
  113.  
  114. /*****************************************************************************/
  115. /*****************************  local functions  *****************************/
  116. /*****************************************************************************/
  117.  
  118. #if !defined(__TURBOC__) && !defined(__JPIC__)
  119. /*
  120.  *    strncmpi() ->    strncmp(), ignore case
  121.  */
  122. static int strncmpi(s, t, n)
  123.     char    *s,
  124.             *t;
  125.     int        n;
  126.     {
  127.     for (; n-- && (tolower(*s) == tolower(*t)); ++t)
  128.         if (!*s++)
  129.             return (0);    /* equal */
  130.  
  131.     if (n < 0)        /* maximum hit */
  132.         return (0);        /* equal */
  133.  
  134.     return ((tolower(*s) > tolower(*t)) ? 1 : (-1));    /* not equal */
  135.     }
  136. #endif
  137.  
  138. /*
  139.  *    END of bmg.c
  140.  */
  141.  
  142. #else
  143.  
  144. /*
  145.  * Replacement search (Warning: Changes buffer argument if ignore case!)
  146.  * Written by P.J. Muller
  147.  */
  148.  
  149. #include <stdio.h>
  150.  
  151. void bmgCompile(char *s, bmgARG *pattern, int ignore_case)
  152. {
  153.   strcpy(pattern->pat, s);
  154.   if ((pattern->ignore = (char) ignore_case) != 0)
  155.       strlwr(pattern->pat);
  156. } /* bmgCompile */
  157.  
  158. int bmgSearch(char *buffer, int buflen, bmgARG *pattern)
  159. {
  160.   if (pattern->ignore)
  161.     strlwr(buffer);        /* !!! modifies argument !!! */
  162.   buffer[buflen] = '\0';    /* dangerous */
  163.  
  164.   return (strstr(buffer,pattern->pat) != NULL);
  165. } /* bmgSearch */
  166.  
  167. #endif
  168.